/////////////////////////////////////////////////////////////////////////
//
// Amuse Engine SDK - core/containers
// Copyright( c) 2014.  All Rights Reserved
//
// File:		AEBaseMap.h
// Author:		Gianluca Belardelli
// Date:		07/05/2014
//
/////////////////////////////////////////////////////////////////////////
#ifndef _AEBASEMAP_H_
#define _AEBASEMAP_H_

/// Default operations for AEMaps
template <typename KEY>
struct AEMapOperations
{
	AE_FORCEINLINE static AEUINT32 Hash( KEY tKey, AEUINT32 uiMod )
	{
		// We ignore the lowest four bits on the address, since most addresses will be 16-byte aligned
		// knuths multiplicative golden hash
		return AEUINT32( ( AEUINT32( tKey ) >> 4 ) * 2654435761U) & uiMod;
	}

	AE_FORCEINLINE static void Invalidate( KEY &tKey )
	{
		tKey = KEY(-1);
	}

	AE_FORCEINLINE static AEBOOL32 IsValid( KEY tKey )
	{
		return tKey != KEY(-1);
	}

	AE_FORCEINLINE static AEBOOL32 Equal( KEY tKey0, KEY tKey1 )
	{
		return tKey0 == tKey1;
	}
};

// Specialized version without shifting away the bottom bits
template <>
struct AE_COREDLLIMPEXP AEMapOperations<AEINT32>
{
	AE_FORCEINLINE static AEUINT32 Hash( AEINT32 tKey, AEUINT32 uiMod ) { return (AEUINT32(tKey) * 2654435761U) & uiMod; }
	AE_FORCEINLINE static void Invalidate( AEINT32 &tKey ) { tKey = AEINT32(-1); }
	AE_FORCEINLINE static AEBOOL32 IsValid( AEINT32 tKey ) { return tKey != AEINT32(-1); }
	AE_FORCEINLINE static AEBOOL32 Equal( AEINT32 nKey0, AEINT32 nKey1 ) { return nKey0 == nKey1; }
};

#define AE_MAP_INDEX_TO_ITERATOR(i) reinterpret_cast<AEMapIterator>( AEUINT32(i) )
#define AE_MAP_ITERATOR_TO_INDEX(it) static_cast<AEINT32>( reinterpret_cast<AEUINT32>(it) )

/// A class to store tKey, value pairs.
/// Note that the tKey must have an invalid or reserved state which is used to mark
/// empty slots. For instance by default -1 is disallowed as a integer tKey. You can override
/// this behavior by instantiating with a custom operations structure.
template <typename KEY, typename VAL=KEY, typename OPS=AEMapOperations<KEY> >
class AEBaseMap
{
// Members
protected:
	/// For creating an uninitialized map.
	enum AEInternalInitializer
	{
		UNINITIALIZED,
	};

	// Internal flags, set in constructor.
	enum
	{
		NUM_ELEMS_MASK = AEINT32(0x7FFFFFFF),
		DONT_DEALLOCATE_FLAG = AEINT32(0x80000000) // Indicates that the storage is not the array's to delete
	};

	struct AEMapPair
	{
		KEY tKey;
		VAL tVal;
	};

	AEMapPair		*m_mpElem;
	AEINT32 		m_nNumElems; // high bits are flags
	AEINT32 		m_nHashMod; // capacity - 1

public:
	/// AEMapIterator type.
	/// All iterators are invalidated after a mutating operation, i.e., insertion, removal.
	typedef class DummyIterator *AEMapIterator;
	
// Methods
protected:
	/// Create an uninitialized map. For internal use.
	AEBaseMap( AEInternalInitializer ii ) {}
	AEUINT32 resizeTable( AEMemoryAllocator& maAlloc, AEINT32 nNewCapacity );
	
	static AE_FORCEINLINE AEBOOL32 isPower2( AEUINT32 uiVal );
	
public:
	AE_DECLARE_NONVIRTUAL_CLASS_ALLOCATOR( TOBEDEFINED, AEBaseMap );

	/// Create an empty pointer map.
	AEBaseMap( void ) : m_mpElem( 0L ), m_nNumElems( 0 ), m_nHashMod( -1 ) {}

	/// Create pointer map initially using preallocated memory block.
	/// Use the getSizeInBytesFor(AEINT32 numKeys) method to find the buffer size
	/// required for a given number of keys.
	AEBaseMap( void* lpPtr, AEINT32 nSizeInBytes );

	/// Destroy a pointer map.
	~AEBaseMap( void );
		
	/// Get an AEMapIterator over the keys of this map.
	AE_FORCEINLINE AEMapIterator GetIterator( void ) const;

	/// Get the tKey at AEMapIterator i.
	AE_FORCEINLINE KEY GetKey( AEMapIterator miIterator ) const;

	/// Get the value at AEMapIterator i.
	VAL GetValue( AEMapIterator miIterator ) const;

	/// Overwrite the value at AEMapIterator i.
	void SetValue( AEMapIterator miIterator, VAL tVal );

	/// Get the next AEMapIterator after i.
	AEMapIterator GetNext( AEMapIterator miIterator ) const;

	/// Return if the AEMapIterator has not reached the end.
	AEBOOL32 IsValid( AEMapIterator miIterator ) const;

	/// Insert tKey with associated value tVal. Keys are unique and by default
	/// (if using hkPointerMapOperations) cannot be -1.
	/// If tKey already exists it is overwritten.
	AEBOOL32 Insert( AEMemoryAllocator &maAlloc, KEY tKey, VAL tVal );

	/// Try to insert tKey with associated value tVal. Keys are unique and by default
	/// (if using hkPointerMapOperations) cannot be -1.
	/// If tKey already exists it is overwritten.
	AEBOOL32 TryInsert( AEMemoryAllocator &maAlloc, KEY tKey, VAL tVal, AEUINT32 &uiRes );

	/// Get an AEMapIterator at 'tKey'. Check if tKey was found with isValid().
	AEMapIterator FindKey( KEY tKey ) const;

	/// If tKey is present return its AEMapIterator, else insert (tKey,tVal) and return the new AEMapIterator.
	/// Thus the returned AEMapIterator is always valid.
	AEMapIterator FindOrInsertKey( AEMemoryAllocator &maAlloc, KEY tKey, VAL tVal );

	/// Shortcut for isValid(findKey(tKey)).
	AE_FORCEINLINE AEBOOL32 HasKey( KEY tKey ) const;

	/// Return the value associated with tKey or def if not present.
	VAL GetWithDefault( KEY tKey, VAL tVal ) const;

	/// If tKey present, write value into out and return HK_SUCCESS. Otherwise return HK_FAILURE.
	AEUINT32 Get( KEY tKey, VAL *lpOut ) const;

	/// Remove AEMapPair at AEMapIterator. The AEMapIterator is no longer valid after this call.
	void Remove( AEMapIterator miIterator );

	/// If tKey present, remove it and return HK_SUCCESS. Otherwise return HK_FAILURE.
	AEUINT32 Remove( KEY tKey );

	/// Return the number of keys.
	AE_FORCEINLINE AEINT32 GetSize( void ) const;

	/// Return the number of keys possible to store without reallocation.
	AE_FORCEINLINE AEINT32 GetCapacity( void ) const;

	/// Return the amount of allocated memory in bytes. Use for statistics.
	AEINT32 GetMemSize( void ) const;

	/// Return the start address in memory of the hashmap. Use for statistics.
	AE_FORCEINLINE void *GetMemStart( void ) const;

	/// Perform an internal consistency check.
	AEBOOL32 IsOk( void ) const;

	/// Remove all keys from the map.
	void Clear( void );

	/// Remove all keys from the map.
	void ClearAndDeallocate( AEMemoryAllocator &maAlloc );

	// Estimates and sets the appropriate table size for a given number of elements.
	void Reserve( AEMemoryAllocator &maAlloc, AEINT32 nNumElements );

	/// Return true if the map was constructed with a buffer which was too small.
	AE_FORCEINLINE AEBOOL32 WasReallocated( void ) const;

	/// Advanced use only.
	void SetOwnedData( void *lpPtr, AEINT32 nSize, AEINT32 nCapacity );

	/// Calculates buffer size required to store the specified number of keys.
	static AEINT32 AE_CALL GetSizeInBytesFor( AEINT32 nNumOfKeys );

	/// Contains the implementation of AEBaseMap(void* lpPtr, AEINT32 nSizeInBytes).
	/// For internal use only.
	void Init( void* lpPtr, AEINT32 nSizeInBytes );
};

#include "AEBaseMap.inl"

#endif // _AEBASEMAP_H_

